package com.gitee.feizns.explore.data_structure.union_find;

/**
 * @author feizns
 * @since 2020/3/11
 */
public class NumIslands {

    public static void main(String[] args) {
        UF uf = new UF(0);
    }

    static int r;
    static int c;

    public static int numIslands(char[][] grid) {
        if ( grid == null || grid.length == 0 || grid[0].length == 0 )
            return 0;
        r = grid.length;
        c = grid[0].length;
        int size = r * c;
        UF uf = new UF(size + 1);
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                int index = node(i, j);
                if ( grid[i][j] == '0' )
                    uf.union(index, size);
                else {
                    int tmp;
                    if ( (tmp = node(i + 1, j)) != -1 && grid[i + 1][j] == '1' )
                        uf.union(tmp, index);
                    if ( (tmp = node(i - 1, j)) != -1 && grid[i - 1][j] == '1' )
                        uf.union(tmp, index);
                    if ( (tmp = node(i, j + 1)) != -1 && grid[i][j + 1] == '1' )
                        uf.union(tmp, index);
                    if ( (tmp = node(i, j - 1)) != -1 && grid[i][j - 1] == '1' )
                        uf.union(tmp, index);
                }
            }
        }
        return uf.count() - 1;
    }

    private static int node(int x, int y) {
        return x >= 0 && x < r && y >= 0 && y < c ? x * c + y : -1;
    }

    static class UF {
        private int[] parents;
        private int[] ranks;
        private int count;
        public UF(int size) {
            parents = new int[size];
            ranks = new int[size];
            for (int i = 0; i < size; i++)
                parents[i] = i;
            count = size;
        }
        public int count() { return count; }
        public void union(int p, int q) {
            int pr = find(p);
            int qr = find(q);
            if ( pr != qr ) {
                if ( ranks[pr] < ranks[qr] )
                    parents[pr] = qr;
                else if ( ranks[pr] > ranks[qr] )
                    parents[qr] = pr;
                else {
                    parents[pr] = qr;
                    ranks[qr]++;
                }
                count--;
            }
        }
        public int find(int q) {
            while ( q != parents[q] ) {
                parents[q] = parents[parents[q]];
                q = parents[q];
            }
            return q;
        }
    }

}
